package main

import "fmt"

var (
	PU = [][]int{
		{0, 0, 0, 7, 2, 8, 0, 0, 0},
		{0, 9, 0, 0, 5, 1, 6, 0, 0},
		{0, 0, 0, 0, 6, 0, 0, 8, 2},
		{3, 0, 0, 8, 0, 2, 7, 0, 4},
		{1, 7, 4, 0, 3, 0, 0, 2, 0},
		{2, 8, 0, 5, 0, 0, 0, 3, 0},
		{0, 1, 0, 3, 0, 0, 2, 0, 0},
		{0, 0, 7, 0, 4, 6, 0, 0, 5},
		{0, 0, 6, 1, 0, 0, 0, 4, 9}}
)

func Show() {
	fmt.Println("-------------------")
	for _, v := range PU {
		fmt.Println(v)
	}
}

func IsValid(row, col int) bool {
	num := PU[row][col]
	for i := 0; i < 9; i++ {
		if (row != i && PU[i][col] == num) || (col != i && PU[row][i] == num) {
			return false
		}
	}

	start_row := row / 3 * 3
	start_col := col / 3 * 3

	for i := start_row; i < start_row+3; i++ {
		for j := start_col; j < start_col+3; j++ {
			if i != row && j != col && PU[i][j] == num {
				return false
			}
		}
	}

	return true
}

func Try(n int) {
	if n >= 81 {
		Show()
		return
	}

	var row, col = n / 9, n % 9
	if PU[row][col] != 0 {
		Try(n + 1)
		return
	}

	for i := 1; i <= 9; i++ {
		PU[row][col] = i
		if IsValid(row, col) {
			Try(n + 1)
		}
	}

	PU[row][col] = 0
}

func main() {
	Show()
	Try(0)
}
